//
// Created by 高森森 on 2022/1/29.
//

#ifndef LEETCODE_SOLUTION15_H
#define LEETCODE_SOLUTION15_H

#include <iostream>
#include <vector>
#include <queue>
#include<unordered_map>
using namespace std;
class Solution15 {
public:
    vector<vector<int>>memory;
    bool dfs(vector<vector<int>>&prerequsites,int start,int target){
        if(memory[start][target]==1)//start是target的先修磕碜
            return true;
        if(memory[start][target]==-1)//不是先修课程
            return false;
        for(auto neigh:prerequsites[start]){
            if(dfs(prerequsites,neigh,target)){
                memory[start][target]=1;
                return true;
            }
        }
        memory[start][target]=-1;
        return false;
    }
    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        vector<bool>result;
        memory.assign(numCourses,vector<int>(numCourses));
        vector<vector<int>>adjact(numCourses);
        for(auto i:prerequisites){
            adjact[i[0]].push_back(i[1]);
            memory[i[0]][i[1]]=1;
        }
        for(auto i:queries){
            result.push_back(dfs(adjact,i[0],i[1]));
        }
        return result;
    }

    vector<bool> checkIfPrerequisite2(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        vector<bool>result;
        memory.assign(numCourses,vector<int>(numCourses));
        vector<vector<int>>adjact(numCourses);
        for(auto i:prerequisites){
            adjact[i[0]].push_back(i[1]);
        }
        for(int i=0;i<numCourses;i++)
        {
            queue<int>que;
            que.push(i);
            while(!que.empty()){
                int node=que.front();
                que.pop();
                for(int neigh:adjact[node]){
                    if(memory[i][neigh]!=1){
                        memory[i][neigh]=1;
                        que.push(neigh);
                    }
                }
            }
        }
        for(auto q:queries){
            result.push_back(memory[q[0]][q[1]]);
        }
        return result;
    }
    //floyd算法
    vector<bool> checkIfPrerequisite3(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        vector<bool> result;
        int n=numCourses;
        vector<vector<bool>> dp(n,vector<bool>(n,0));
        for(auto p:prerequisites){
            dp[p[0]][p[1]]= true;
        }
        for(int k=0;k<n;k++){
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    dp[i][j]=dp[i][j]||(dp[i][k]&&dp[k][j]);
                }
            }
        }
        for(auto &q:queries){
            result.push_back(dp[q[0]][q[1]]);
        }
        return result;
    }
};


#endif //LEETCODE_SOLUTION15_H
